package prerequisites;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

/**
 * Level 1000 difficulty. 
 * Not hard to come up with a solution but very complicated.
 * @author Qu huanwen
 *
 */
public class Prerequisites {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Prerequisites inst = new Prerequisites();
		print(inst.orderClasses(new String[] { "CSE121: CSE110", "CSE110:",
				"MATH122:" }));
		print(inst.orderClasses(new String[] { "ENGL111: ENGL110",
				"ENGL110: ENGL111" }));
		print(inst.orderClasses(new String[] { "ENGL111: ENGL110" }));
		print(inst.orderClasses(new String[] { "CSE258: CSE244 CSE243 INTR100",

		"CSE221: CSE254 INTR100", "CSE254: CSE111 MATH210 INTR100",
				"CSE244: CSE243 MATH210 INTR100", "MATH210: INTR100",
				"CSE101: INTR100", "CSE111: INTR100", "ECE201: CSE111 INTR100",
				"ECE111: INTR100", "CSE243: CSE254", "INTR100:" }));
	}

	private static void print(String[] a) {
		for (String s : a)
			System.out.print(s + " ");
		System.out.println();
	}

	static private class Cls implements Comparable<Cls> {
		String name;
		String dept;
		int num;

		public Cls(String s) {
			this.name = s;
			dept = s.substring(0, s.length() - 3);
			num = Integer.parseInt(s.substring(s.length() - 3));
		}

		public boolean equals(Object o) {
			Cls c = (Cls) o;
			return name.equals(c.name);
		}

		@Override
		public int compareTo(Cls c) {
			if (num < c.num)
				return -1;
			else if (num > c.num)
				return 1;
			else
				return dept.compareTo(c.dept);
		}

		public String toString() {
			return name;
		}
	}

	static private class Scheudle implements Comparable<Scheudle> {
		Cls c1, c2;

		public Scheudle(String s1, String s2) {
			if (s1 != null)
				c1 = new Cls(s1);
			c2 = new Cls(s2);
		}

		public boolean equals(Object o) {
			Scheudle s = (Scheudle) o;
			if (c1 == c2)
				return true;
			if (c1 == null || c2 == null)
				return false;
			return c1.equals(s.c1) && c2.equals(s.c2);

		}

		@Override
		public int compareTo(Scheudle o) {
			if (c1 == null && o.c1 != null)
				return -1;
			if (c1 != null && o.c1 == null)
				return 1;
			return c2.compareTo(o.c2);
		}

		public String toString() {
			return c1 + " -> " + c2;
		}
	}

	public String[] orderClasses(String[] classSchedule) {
		List<String> list = new ArrayList<String>();
		TreeSet<Scheudle> set = parse(classSchedule);
		try {
			while (!set.isEmpty()) {
				Scheudle s = set.pollFirst();
				if (s.c1 != null) {
					throw new Exception("");
				}
				set = removeClass(set, s.c2);
				list.add(s.c2.name);
			}

			return list.toArray(new String[] {});
		} catch (Exception e) {
			return new String[] {};
		}
	}

	private TreeSet<Scheudle> removeClass(TreeSet<Scheudle> set, Cls c)
			throws Exception {
		TreeSet<Prerequisites.Scheudle> set2 = new TreeSet<Prerequisites.Scheudle>();
		for (Scheudle s : set) {
			if (s.c1 != null && s.c1.equals(c)) {
				s.c1 = null;
			} else if (s.c2 != null && s.c2.equals(c)) {
				throw new Exception("");
			}
			set2.add(s);
		}
		return set2;
	}

	private TreeSet<Prerequisites.Scheudle> parse(String[] classSchedule) {
		TreeSet<Prerequisites.Scheudle> set = new TreeSet<Prerequisites.Scheudle>();
		for (String s : classSchedule) {
			String t[] = s.split(":");
			if (t.length == 1) {
				set.add(new Scheudle(null, t[0]));
			} else {
				String cs[] = t[1].trim().split(" ");
				for (String c : cs) {
					set.add(new Scheudle(c, t[0]));
				}
			}
		}
		return set;
	}
}
